package leetcode.f1t100;

import java.util.ArrayList;
import java.util.List;

/**
 * 生成以0~((2^n)-1) 共 2^n个数字组成的格雷码(相邻两个数二进制只有一个位置不同, 且首位相连)
 * https://leetcode.com/problems/gray-code/description/
 *
 * @author lichx
 * @createTime 2024/2/4 16:39
 */
public class Q89_GrayCode {

    public static void main(String[] args) {
        Q89_GrayCode bean = new Q89_GrayCode();
        List<Integer> list = bean.grayCode(4);
        for (Integer i : list) {
            System.out.println(i);
        }
    }

    public List<Integer> grayCode(int n) {
        List<Integer> list = new ArrayList<>((1 << n));
        list.add(0);
        list.add(1);
        boolean flag = true;
        for (int i = 1; i < n; i++) {
            int preStart = 1 << (i -1), preEnd = (1 << i) ;
            for (int j = preStart; j < preEnd; j++) {
                Integer preVar = list.get(j);
                if (flag){
                    list.add((preVar << 1) + 1);
                    list.add(preVar << 1);
                }else {
                    list.add(preVar << 1);
                    list.add((preVar << 1) + 1);
                }
                flag = !flag;
            }
        }
        return list;
    }
}
